package random_test;

import java.util.*;

public class Test_0301 {

    // 2583. 二叉树中的第 K 大层和
    public long kthLargestLevelSum(TreeNode root, int k) {
        // 1. 利用队列进行层次遍历
        // 2. 利用小根堆统计第 k 大层和
        Queue<TreeNode> q = new LinkedList<>();
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        q.offer(root);

        while(!q.isEmpty()) {
            int sz = q.size();
            long sum = 0;
            while(sz-- > 0) {
                TreeNode t = q.poll();
                sum += t.val;
                if(t.left != null) q.offer(t.left);
                if(t.right != null) q.offer(t.right);
            }

            minHeap.add(sum);
            if(minHeap.size() > k) minHeap.poll();
        }

        return minHeap.size() == k ? minHeap.peek() : -1;
    }




    // 300. 最长递增子序列
    public int lengthOfLIS(int[] nums) {
        // dp[i]: 以 i 位置为结尾的所有子序列中最长子序列的长度
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        int ret = 1;
        for(int i = 1; i < n; i++) {
            for(int j = i - 1; j >= 0; j--) {
                if(nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }


    // 416. 分割等和子集
    public boolean canPartition(int[] nums) {
        int sum = 0, n = nums.length;
        for(int x : nums) sum += x;
        if(sum % 2 == 1) return false;
        sum /= 2;

        // dp[i][j]: 在前 i 个数中，能否凑出和为 j 的情况
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;

        for(int i = 1; i <= n; i++)
            for(int j = sum; j >= nums[i - 1]; j--) {
                dp[j] = dp[j] || dp[j - nums[i - 1]];
            }
        return dp[sum];
    }
}
